package formal.linkedList;

import java.util.Arrays;

/**
 * 分隔链表
 *
 * @author DengYuan2
 * @create 2021-01-09 14:58
 */
public class M_725 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        ListNode n7 = new ListNode(7);
        ListNode n8 = new ListNode(8);
        ListNode n9 = new ListNode(9);
        ListNode n10 = new ListNode(10);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n8;
        n8.next = n9;
        n9.next = n10;

        ListNode[] listNodes = splitListToParts(n1, 3);
        System.out.println(Arrays.toString(listNodes));

    }


    /**
     * 我的写法，同官方的思想相近
     *
     * @param root
     * @param k
     * @return
     */
    public static ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] listNodes = new ListNode[k];
        int size = 0;
        ListNode tmp = root;
        while (tmp != null) {
            size++;
            tmp = tmp.next;
        }
//        tmp = root;
//        if (size<=k){
//            for (int i = 0; i < size; i++) {
//                listNodes[i]=tmp;
//                tmp=tmp.next;
//                listNodes[i].next=null;
//            }
//        }else {
//            //存放每部分的节点个数
//            int[] counts = new int[k];
//            int count = size/k;
//            Arrays.fill(counts,count);
//            int carry = size%k;
//            for (int i = 0; i < carry; i++) {
//                counts[i]++;
//            }
//            tmp = root;
//            for (int i = 0; i < k; i++) {
//                count = counts[i];
//                listNodes[i]=tmp;
//                for (int j = 0; j < count-1; j++) {
//                    tmp=tmp.next;
//                }
//                ListNode node = tmp.next;
//                tmp.next=null;
//                tmp=node;
//            }
//        }
        // 根据大神的写法，可修改如下
        int count = size / k;
        int carry = size % k;
        tmp = root;
        //将两种情况放到一起，第一种情况用tmp!=null来解决
        for (int i = 0; i < k && tmp != null; i++) {
            //carry每次都要-1哦
            int curCount = count + ((carry-- > 0) ? 1 : 0);
            listNodes[i] = tmp;
            for (int j = 0; j < curCount - 1; j++) {
                tmp = tmp.next;
            }
            ListNode node = tmp.next;
            tmp.next = null;
            tmp = node;
        }
        return listNodes;
    }
}
